A rate color marker can meter packets in a traffic stream and mark the packets based on traffic parameters. Such metering and marking can be used to enable services such as quality of service or congestion control in communication networks. Two similar color rate markers are documented in Internet Engineering Task Force (IETF) Informational Request For Comments (RFC) 2697 and 2698. See Heinanen, J. and R. Guerin, “A Single Rate Three Color Marker”, RFC 2697, September, 1999, and Heinanen, J. and R. Guerin, “A Two Rate Three Color Marker”, RFC 2698, September, 1999.
The referenced RFCs describe color rate marker algorithms in the context of an Internet Protocol (IP)-based packet switched internetwork. However, such algorithms can be implemented in cell-switched networks as well. Each color marker meters a traffic stream, for example, an IP packet stream, and marks its packets one of green, yellow or red.
The Single Rate Three Color Marker (srTCM) described in RFC2697 marks packets in an IP stream based on a traffic rate, Committed Information Rate (CIR), and two different burst sizes, Committed Burst Size (CBS), and Excess Burst Size (EBS). In short, a packet is marked green if it does not exceed CBS, yellow if it does exceed CBS but does not exceed EBS, and red if it exceeds both CBS and EBS. srTCM is limited in that it uses the length, but not peak rate, of a burst of traffic to determine the color associated with the traffic. A service, or a level of service, is then provided to the traffic based on its color.
The Two Rate Three Color Marker (trTCM) described in RFC 2698 marks packets in an IP stream based on two different traffic rates, Peak Information Rate (PIR), and Committed Information Rate (CIR), and corresponding burst sizes Committed Burst Size (CBS) and Peak Information Burst (PBS). According to trTCM, a packet is marked red if it exceeds PIR, and if the packet does not exceed PIR, it is marked yellow or green depending on whether it exceeds CIR or does not exceed CIR. By making use of two rates, a peak traffic rate (or simply, peak rate), and a committed rate, trTCM is able to monitor peak rate traffic separate from committed rate traffic.
Both srTCM and trTCM contemplate a metering device that meters each packet in a traffic stream and forwards, or passes, the packet to a marker that colors the packet. Both algorithms operate in one of two modes, color-blind mode, in which the meter receives the traffic stream as if it is uncolored, and color-aware mode, in which packets in the received traffic stream are already colored (“pre-colored”), for example, one of colors green, yellow, and red. The details of the pre-coloring process and how the meter detects or determines the color of a packet is implementation specific and outside the scope of the RFCs as well as this invention. The RFCs disclose the marker recoloring a packet based on the results of the meter, and provide, as an example, coding the color as a codepoint in the DiffServ (DS) field of the packet in a per-hop behavior (PHB) specific manner, and refers one to IETF RFC2474 for further information. See Nichols, K., Blake, S., Baker, F. and D. Black, “Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers”, RFC 2474, December, 1998. The color can be coded as a drop precedence of the packet, according to RFC2597. See Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z. and W. Weiss, “An Architecture for Differentiated Services”, RFC 2475, December 1998.
Both color markers can mark packets in a traffic stream, for example, such that different levels of assurance are provided to packets based on whether the packets are green, yellow or red. Decreasing levels of service may be provided to green, then yellow, then red, packets. For example, green packets may be guaranteed delivery, or at least forwarded with a low probability of being discarded or dropped, while yellow packets may be forwarded on a best effort basis, and red packets dropped.
The srTCM meter operates in either color-blind or a color-aware mode, and uses two token buckets, C and E, into which tokens are added at the same rate, CIR. In an IP context, CIR is expressed in terms of bytes per second, more specifically, in terms of IP bytes per second. The token buckets initially are full, defined by CBS for token bucket C (hence the token bucket's name) and EBS for token bucket E (and hence its name). That is, the number of tokens, or simply, token count, is initially set to CBS and EBS for token buckets C and E, respectively. CBS and EBS are measured, for example, in bytes. Thus, in an IP network, typically the value of CBS or EBS is at least equal to the largest possible IP packet received by the meter. srTCM token buckets are depleted, that is, the token count is decremented, when processing received packets, wherein the number of bytes in the received packet determines whether and how much the token count is decremented. Both token buckets are filled with tokens at rate CIR: in token bucket C, tokens are added, that is, the token count Tc incremented, at rate CIR up to CBS, and the token count Te for token bucket E is also incremented at rate CIR up to EBS (only when Tc=CBS).
The trTCM meter also operates in color-blind and color-aware mode, and uses two token buckets, P and C, into which tokens are added at different rates, PIR and CIR. Both rates are also expressed in terms of IP bytes per second in an IP network context. The token buckets initially are full, defined by PBS for token bucket P and CBS for token bucket C. The relationship between PBS and CBS can be defined as follows:PBS=CBS+EBS trTCM token buckets are depleted, that is, the token count is decremented, when processing received packets, as in srTCM. However, the token buckets are filled with tokens at different rates. In token bucket P, tokens are added, that is, the token count Tp incremented, at rate PIR up to PBS, whereas the token count Tc for token bucket C is incremented at rate CIR up to CBS.
In color-aware mode, trTCM recolors a green packet green only when sufficient tokens are available in both token buckets C and P. This can lead to a situation in which a green packet is received and recolored red even though there are sufficient tokens in token bucket C, as can happen when token bucket P has insufficient tokens to process the green packet due to the previous processing of received yellow packets. When this situation arises, transmission of green packets cannot be guaranteed even when the green packets conform to a traffic profile defined by CBS and CIR. Thus, in some situations, a network service provider using trTCM is unable to guarantee transmission of green packets. This nondeterministic transmission of green packets by trTCM defeats one of the primary objects of color rate marking, which is provisioning a network that guarantees transmission of green packets.
One approach to solving this problem is to modify the trTCM algorithm as follows:                1) change the rate at which the token count is incremented, that is, the rate at which tokens are deposited, in token bucket P from PIR to PIR−CIR;        2) change the maximum size of token bucket P from PBS to PBS−CBS;        3) change the trTCM algorithm such that the availability of tokens in token bucket C is checked first; and        4) change the trTCM algorithm such that packets which will be marked green only remove tokens from token bucket C.        
These modifications solve the original problem, but introduce a new one: in the absence of incoming green packets, the rate at which incoming yellow packets will be marked as yellow is limited to PIR-CIR instead of PIR. This can be a significant issue because when network bandwidth reserved for committed rate traffic goes unused, it cannot be reclaimed for use by peak rate traffic, resulting in underutilization of the network and, in the case of a network service provider that sells network bandwidth, lost revenue.
Another proposed solution to the RFC2698 problem is to allow green packets to borrow future tokens from token bucket P (which can cause the token count in token bucket P to become negative), thus preventing recoloring a green packet to red in the case where there are sufficient tokens in the token bucket C but not the token bucket P. This solution has two problems. The first problem is that if a PBS burst of yellow packets occurs, followed by a CBS burst of green packets, all packets will be passed as originally marked but the resultant combined burst will be of size PBS+CBS which violates the traffic profile. This can be addressed by reducing the size of token bucket P to PBS−CBS, or by keeping its size at PBS but reserving a CBS-size amount of Tp tokens for green packets. In any case, the second problem is that a conformant burst of yellow and green packets may result in some of the yellow packets being recolored red, depending on the sequence of the packets.